from mip import Model, CONTINUOUS, BINARY, xsum, minimize

big_M = 1000
N = 4
running_time = [10, 14, 18, 6]
loading_time = [60, 90, 120, 130]

model = Model()
x = {(i, j, s): model.add_var(var_type=BINARY) for i in range(N) for j in range(N) for s in [0, 1]}
y_start = {(i, s): model.add_var(var_type=BINARY) for i in range(N) for s in [0, 1]}  # 是否为取车开始点
y_end = {(i, s): model.add_var(var_type=BINARY) for i in range(N) for s in [0, 1]}  # 是否为取车结束点

t = {(i, s): model.add_var(var_type=CONTINUOUS, lb=0) for i in range(N) for s in [0, 1]}
t_e = model.add_var(var_type=CONTINUOUS, lb=0)
t_half = model.add_var(var_type=CONTINUOUS, lb=0)
for s in [0, 1]:
    model += xsum(y_start[i, s] for i in range(N)) == 1
    model += xsum(y_end[i, s] for i in range(N)) == 1
for i in range(N):
    for s in [0, 1]:
        model += xsum(x[i, j, s] for j in range(N) if i != j) + xsum(x[j, i, s] for j in range(N) if i != j) >=1
        model += xsum(x[i, j, s] for j in range(N) if i != j) - xsum(x[j, i, s] for j in range(N) if i != j) == y_start[i, s] - y_end[i, s]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            for s in [0, 1]:
                model += t[j, s] - t[i, s] >= (x[i, j, s] - 1) * big_M + running_time[j] + running_time[i]
            model += t[j, 1] - t[i, 0] >= running_time[j] + running_time[i]

for i in range(N):
    model += t[i, 0] >= y_start[i, 0] * running_time[i]
    model += t[i, 1] - t[i, 0] >= loading_time[i]

for i in range(N):
    model += t_e >= t[i, 1]

model.objective = minimize(t_e + xsum(y_end[i, 1] * running_time[i] for i in range(N)))

# 求解
# model.write("model.lp")
model.max_mip_gap = 0.01
model.verbose = 0
model.optimize(max_seconds=300)

# 输出
if model.num_solutions:
    print('目标函数值:', format(model.objective_value))
    for s in [0, 1]:
        route = []
        for i in range(N):
            if y_start[i, s].x == 1:
                cur_node = i
                route.append(str(i+1))
        while y_end[cur_node, s].x != 1:
            for j in range(N):
                if x[cur_node, j, s].x == 1:
                    if cur_node != j:
                        route.append(str(j+1))
                    cur_node = j
        print('{0}顺序：{1}'.format('取车' if s==1 else '送车', '->'.join(route)))